# -*- coding: utf-8 -*-

''' 
Autores: 
Pedro Godinho - 6355
Pedro Lopes - 9850
'''

import math
from random import uniform
import time
import matplotlib.pyplot as plt

''' Class responsable for HeapSort algorithm and tests'''
class HeapSort:
    def max_heapify(self, A, i):
        global HEAPSIZE

        l = 2 * i
        r = l + 1

        if(l <= HEAPSIZE and A[l] > A[i]):
            largest = l
            pass
        else:
            largest = i
            pass

        if(r <= HEAPSIZE and A[r] > A[largest]):
            largest = r
            pass

        if(largest != i):
            A[i], A[largest] = A[largest], A[i]
            self.max_heapify(A, largest)
            pass

    def build_max_heap(self, A):
    	global HEAPSIZE
    	HEAPSIZE = len(A) - 1

    	for i in range((int) (math.floor(HEAPSIZE / 2)), 0, -1):
    		self.max_heapify(A,i)
    		pass
    	pass

    '''@param A: list to sort'''
    def heapsort(self, A):
    	global HEAPSIZE

    	self.build_max_heap(A)
    	for i in range(len(A)-1, 0,-1):
    		A[0], A[i] = A[i], A[0]
    		HEAPSIZE = HEAPSIZE - 1
    		self.max_heapify(A, 0)
    		pass
    	pass

    def grafico(self):
        Z = [1] + range(50, 1050, 50)
        T = []
        M = 50
        for n in Z:
            A = [ uniform(0.00,1.0) for k in xrange(n)]
            tempos = []
            for k in range(M):
                t1 = time.time()
                self.heapsort(A)
                t2 = time.time()
                tempos.append(t2-t1)
            media = reduce(lambda x, y: x + y, tempos) / len(tempos)
            var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
        
            T.append((n,media, var))

        X = [n for n, media, var in T]
        Y = [media for n, media, var in T]
        ct = 6e5
        Z = [ (n * (math.log(n)))/ct for n, media, var in T]


        plt.grid(True)
        plt.ylabel(u'T(n) - tempo de execução médio em segundos')
        plt.xlabel(u'n - número de elementos')
        plt.plot(X,Y,'rs', label="resultado experimental")
        plt.plot(X, Z, 'b^', label=u"previsão teórica")
        plt.title("Heap Sort")
        plt.legend()
        plt.show()
